package edu.cityu.cs.hk.datastructures;
import java.util.Iterator;

/** 
 * Dijkstra's algorithm for the single-source shortest path problem in
 * an undirected graph whose edges have integer weights.  
 *
 * <p>To execute the algorithm, use the {@link
 * #execute(Graph,Vertex,Object) execute} method, and then make
 * subsequent calls to the {@link #getDist(Vertex) getDist} method to
 * obtain the shortest distance from the start to any given vertex.
 *
 * @author Roberto Tamassia, Michael Goodrich, Eric Zamore
 */

//begin#fragment execute
/* Dijkstra's algorithm for the single-source shortest path problem
 * in an undirected graph whose edges have integer weights. 
 */
public class Dijkstra {
  /** Infinity value. */
  public static final int INFINITE = Integer.MAX_VALUE;
  /** Input graph. */
  protected Graph graph;
  /** Decoration key for edge weights */
  protected Object WEIGHT;
  /** Auxiliary priority queue. */
  protected AdaptablePriorityQueue Q;
  /** Executes Dijkstra's algorithm.
    * @param g Input graph
    * @param s Source vertex
    * @param w Weight decoration object
    */
  public void execute(Graph g, Vertex s, Object w) {
    graph = g;
    WEIGHT = w;
    Q = new HeapAdaptablePriorityQueue(new DefaultComparator());
    dijkstraVisit(s);
  }
  /** Get the distance of a vertex from the source vertex.
//end#fragment execute
   * This method returns the length of a shortest path from the source
   * to <tt>u</tt> after {@link #execute(Graph,Vertex,Object) execute}
   * has been called.
//begin#fragment execute
   * @param u Start vertex for the shortest path tree
   */
  public int getDist(Vertex u) {
    return ((Integer) u.get(DIST)).intValue();
  }
//end#fragment execute

  //begin#fragment dijkstraVisit
  /** The actual execution of Dijkstra's algorithm.
    * @param v source vertex.  
    */
  protected void dijkstraVisit (Vertex v) {
    // store all the vertices in priority queue Q
    for (Iterator vertices = graph.vertices(); vertices.hasNext();) {
      Vertex u = (Vertex) vertices.next();
      int u_dist;
      if (u==v)
	u_dist = 0;
      else
	u_dist = INFINITE;

      Entry u_entry = Q.insert(new Integer(u_dist), u);
      setEntry(u, u_entry);
    }
    // grow the cloud, one vertex at a time
    while (!Q.isEmpty()) {
      // remove from Q and insert into cloud a vertex with minimum distance
      Entry u_entry = Q.min();
      Vertex u = getVertex(u_entry);
      int u_dist = getDist(u_entry);
      Q.remove(u_entry); // remove u from the priority queue
      setDist(u, u_dist); // the distance of u is final
      removeEntry(u); // remove the entry decoration of u
      if (u_dist == INFINITE)
	continue; // unreachable vertices are not processed
      // examine all the neighbors of u and update their distances
      for (Iterator edges = graph.incidentEdges(u); edges.hasNext();) {
	Edge e = (Edge) edges.next();
	Vertex z = graph.opposite(u,e);
	Entry z_entry = getEntry(z);
	if (z_entry != null) { // check that z is in Q, i.e., not in the cloud
	  int e_weight = weight(e);
	  int z_dist = getDist(z_entry);
	  if ( u_dist + e_weight < z_dist ) // relaxation of edge e = (u,z)
	    Q.replaceKey(z_entry, new Integer(u_dist + e_weight));
	}
      }
    }
  }
  //end#fragment dijkstraVisit

  //begin#fragment auxiliary
  /** Get the weight of an edge  
   */
  protected int weight(Edge e) {
    return ((Integer) e.get(WEIGHT)).intValue();
  }
  /** Attribute for vertex distances 
   */
  protected Object DIST = new Object();
  /** Set the distance of a vertex. 
   */
  protected void setDist(Vertex v, int d) {
    v.put(DIST, new Integer(d));
  }
  /** Decoration key for entries in the priority queue 
   */
  protected Object ENTRY = new Object();
  /** Get the entry decoration of a vertex. 
   */
  protected Entry getEntry(Vertex v) {
    return (Entry) v.get(ENTRY);
  }
  /** Set the entry decoration of a vertex 
   */
  protected void setEntry(Vertex v, Entry e) {
    v.put(ENTRY, e);
  }
  /** Remove the entry decoration of a vertex 
   */
  protected void removeEntry(Vertex v) {
    v.remove(ENTRY);
  }
  /** Get the vertex associated with an entry 
  */
  protected Vertex getVertex(Entry e) {
    return (Vertex) e.value();
  }
  /** Get the distance of a vertex given its entry 
   */
  protected int getDist(Entry e) {
    return ((Integer) e.key()).intValue();
  }
} // end of Dijkstra class
//end#fragment auxiliary
